package com.jeff.practice;

/**
 * 动态规划求零钱问题
 * 给定不同面额的硬币 coins 和一个总金额 amount，问最少需要多少个硬币凑出这个金额。
 * 假设每种硬币的数量无限，也就是说，我们可以无限次使用每一种硬币。
 * 思路:
 * 1. 定义一个数组 dp，dp[i] 表示凑出金额 i 时最少需要的硬币数量。
 * 2. 初始值 dp[0] = 0，表示凑出 0 时不需要任何硬币。
 * 3. 遍历 coins，对于每一种硬币 coin，遍历 i 到 amount 的所有金额，如果当前金额 i 可以凑出，
 * 则 dp[i] = min(dp[i], dp[i - coin] + 1)，即如果当前金额 i 可以凑出，则最少需要的硬币数量为 dp[i - coin] + 1。
 * 4. 最后返回 dp[amount] 即为最少需要的硬币数量。
 * 时间复杂度：O(amount * n)，n 为 coins 的数量。
 * 空间复杂度：O(amount)，需要额外的空间存储 dp 数组。
 *
 * @author yaojianfeng
 */
public class DynamicProgrammingChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        minCoins(coins, amount);
        minCoins(11);
    }

    /**
     * 求零钱问题，硬币面值可选 coins，总金额 amount
     * 思路：
     * 1. 创建一个数组 dp，dp[i] 表示凑出金额 i 时最少需要的硬币数量。
     * 2. 初始值 dp[0] = 0，表示凑出 0 时不需要任何硬币。
     * 3. 遍历 coins，对于每一种硬币 coin，遍历 i 到 amount 的所有金额，如果当前金额 i 可以凑出，
     * 则 dp[i] = min(dp[i], dp[i - coin] + 1)，即如果当前金额 i 可以凑出，则最少需要的硬币数量为 dp[i - coin] + 1。
     * 4. 最后返回 dp[amount] 即为最少需要的硬币数量。
     *
     * @param coins  硬币面值数组
     * @param amount 总金额
     */

    public static void minCoins(int[] coins, int amount) {
        // 创建一个数组用于存储最少硬币数
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            // 初始化存储最少硬币数的数组
            dp[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                // 判断当前面额的硬币是否小于等于总金额
                if (coin <= i) {
                    // 更新存储最少硬币数的数组
                    dp[i] = Integer.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        // 打印当前金额下的最少硬币数
        System.out.println(dp[amount]);
    }

    /**
     * 求零钱问题，硬币面值只有 1，2，5
     * 思路：
     * 1. 先除以 5，得到整数部分 commonNum，余数部分 leftNum
     * 2. 根据余数部分的不同，确定最少的硬币数
     * 3. 最后返回 commonNum + 最少的硬币数
     *
     * @param amount 总金额
     */
    public static void minCoins(int amount) {
        int commonNum = amount / 5;
        int leftNum = amount % 5;
        int result = switch (leftNum) {
            case 1, 2 -> 1;
            default -> 2;
        };
        System.out.println("最少的硬币数: " + (result + commonNum));
    }

}
